The present invention relates to an apparatus and method for handling memory access requests in a data processing system.
In data processing systems of simple architecture a processor is connected to a main memory through a bus. A simple architecture of this kind has severe performance limitations because of memory latency and memory bandwidth. Because of this, most modern data processing systems have a multi-level memory hierarchy. At the top of the memory hierarchy, directly below the processor, there is provided a fast and small memory element, referred to as a cache memory. There then follows main memory and mass storage. Moreover, two or more levels of cache memory may be provided, for example an internal cache memory located on the same integrated circuit as the processor and an external cache memory located on a separate integrated circuit from the processor.
A typical modern data processing system thus has a multi-level memory hierarchy, with the higher levels of memory being associated with faster access times, i.e. lower latency, and the lower levels with slower access times, i.e. higher latency. However, between each level of the memory hierarchy there still remains a latency differential, and the overall latency difference between the processor, on the one hand, and the main memory or mass storage, on the other hand, still exists, notwithstanding the multi-level memory hierarchy.
Although increasing the memory access times of memories at each level of the memory hierarchy will certainly increase system performance, it is likely that an inherent latency differential between the processor and the memory hierarchy levels will remain a feature of future data processing systems, not only for technical, but also for economic, reasons.
The present invention is thus directed to increasing the efficiency with which memory access requests are handled by a data processing system by means other than speeding up memory access times or increasing memory bandwidth.
More especially, it is an aim of the present invention to provide a method and apparatus for increasing the throughput of memory access requests in a data processing system, independent of memory access times and memory bandwidth.
Particular and preferred aspects of the invention are set out in the accompanying independent and dependent claims. Features of the dependent claims may be combined with those of the independent claims as appropriate and in combinations other than those explicitly set out in the claims.
According to a first aspect of the invention there is provided a memory access request handling unit designed to intercept and re-order the flow of memory access requests output from a source of memory access requests prior to receipt by a target data storage element. Examples of common memory access requests are read requests and write requests. The memory access request handling unit comprises an input for receiving memory access requests and an output for transmitting memory access requests. A queue comprising a plurality of queue elements is arranged to receive, and to store temporarily, memory access requests received at the input pending transmission to the output. Comparison logic is provided that is operable to perform a comparison operation on the memory access requests stored in the queue elements. The result of the comparison operation is to select at least one of the memory access requests for transmission from the queue to the output. In this way, the comparison logic dynamically re-orders the sequence with which memory access requests are supplied to the data storage element.
A memory access request handling unit may be arranged between any two levels in a multi-level system hierarchy. For example, it may be arranged, between a processor and cache memory, between two cache memories at different levels of a memory hierarchy, or between a main memory and a mass storage medium. The mass storage medium may be a CD-ROM, or other mass storage medium such as a hard disk.
In an embodiment of the first aspect of the invention, the memory access request handling unit further comprises a list store comprising a plurality of list elements. Each list element is arranged to store a list entry derived from a memory access request that has previously been transmitted from the queue to the output for as long as that memory access request is being serviced at the data storage element. The comparison logic is arranged to compare ones of the memory access requests stored in the queue elements and the list entries stored in the list store, so as to dynamically select the order in which memory access requests are transmitted from the queue to the output. In this way, the transmission of a memory access request to the data storage element can be suppressed if there is an earlier memory access request still being serviced by the data storage element of the kind which would prevent the servicing of the later memory access request. Conversely, a memory access request stored in the queue can be promoted ahead of other memory access requests stored in the queue, if it can be serviced more rapidly than normal as a result of there being a memory access request currently being serviced by the data storage element of a similar or complementary kind.
In this embodiment, when a memory access request is transmitted from the queue to the output for the data storage element, a list entry is generated. The list entry may include a memory access request-type portion derived from an address portion of the queue element being transmitted. The list entry may also include an identifier portion by which the list entry can be identified on completion of the memory access request and thereby canceled when the data storage element has serviced the memory access request. The comparison logic may be arranged to prevent transmission of any memory access request from the queue to the data storage element which has an address portion that matches the memory access request-type portion of any one of the list entries. Moreover, the comparison logic may be operable preferentially to transmit memory access requests from the queue to the data storage element which have address portions that do not match the memory access request-type portions of any of the list entries.
Taking the example of a cache memory being the data storage element, a memory access request to the same cache line as the previous memory access request can be prevented in the event that the previous memory access request resulted in a cache miss, whereas a memory access request to a different cache line may hit and may thus be allowed to transmit from the queue to the data storage element by the comparison logic.
Taking another example of a main memory being the data storage element, the comparison logic can be arranged to prevent memory access requests being transmitted to any memory bank which is still servicing a previous data request.
In an alternative embodiment of the first aspect of the invention, the queue elements each have a source priority level storage portion arranged to receive a priority value when a memory access request is received at the input. The comparison logic is arranged to compare at least the source priority values of the memory access requests stored in the queue elements, so as to dynamically select the order in which memory access requests are transmitted from the queue to the output. In this way, it is possible to cause a later-generated memory access to reach the data storage element before earlier-generated memory access requests so that memory access requests with a higher priority can be serviced more quickly. The priority value can be determined by an input stage of the memory access request handling unit from attributes of the memory access request using a standard source. Alternatively, the priority value can be explicitly specified in each memory access request by the source, which will need to be specially designed to have this capability.
In a further embodiment of the first aspect of the invention, the features of the above-described embodiments are combined so that the comparison logic is arranged to compare the source priority values of the memory access requests stored in the queue elements with the list entries, so as to dynamically select the order in which memory access requests are transmitted from the queue to the output. Parts of the memory access requests other than the source priority value may also be included in the comparison.
In each of the above-described embodiments additional circuitry associated with the queue and comparison logic, and list if provided, can be interposed in the communication link from the source to the data storage element without having to modify the design of existing memory access request sources and data storage elements. However, in those embodiments that use a source priority value, a modified source is needed in the case that the source priority value is defined at the source. Conversely, a standard source can be used in the case that the source priority value is determined by an input stage of the memory access request handling unit from attributes of a standard format memory access request.
According to a second aspect of the invention there is provided a data processing system including a source of memory access requests, a data storage element for servicing memory access requests generated by the source, and, arranged between the source and data storage element, a memory access request handling unit according to the above-described first aspect of the invention. In use, the memory access request handling unit intercepts and queues memory access requests transmitted from the source and dynamically re-orders the sequence in which they are transmitted to the data storage element, so as to increase overall system performance.
According to third and fourth aspects of the invention, a memory access request handling unit with multiple queues is provided. Moreover, the memory access request handling unit is provided with a router as an input stage. The router is arranged to route the memory access requests received from the source to an appropriate queue. The routing is performed according to a memory access request type classification. The type classification may be made by the router itself on the basis of an analysis of each memory access request. Alternatively, the memory access requests may each contain an explicit type classification added by the source.
The memory access request handling unit of the third aspect of the invention further comprises a list store. The list store has a plurality of list elements. Each list element is arranged to store a list entry derived from a memory access request that has previously been transmitted from one of the queues to the output. Comparison logic is provided and is operable to perform a comparison operation on the memory access requests stored in the queue elements with each of the list entries stored in the list store. As a result of the comparison operation, a selection of at least one or more of the memory access requests is made. The selected memory access request or requests are then transmitted to the output. The provision of multiple queues is exploited by giving a different overall priority level to transmission from the different queues, the different overall queue priority levels being reflected in the comparison operation.
The fourth aspect of the invention provides a memory access request handling unit specifically for memory read requests. Multiple read queues are provided together with comparison logic operable to perform a comparison operation on the memory read requests stored in the queue elements. As a result of the comparison operation, at least one of said memory read requests is selected for transmission to the output. As in the third aspect of the invention the comparison logic additionally prioritizes the selection on a queue-by-queue basis.
As described above, the memory access request handling units according to some embodiments and aspects of the invention require the incoming memory access requests to be tagged with a source priority value.
Accordingly, a fifth aspect of the invention provide a source with this capability. The memory access request source of the fifth aspect of the invention comprises at least first and second memory access request generating units. The source is operable to tag different priority values to memory access requests generated by the respective memory access request generating units. These priority values serve to provide a basis for memory access request type classification by a subsequent memory access request handling unit.
A sixth aspect of the invention provides a method of handling memory access requests in a data processing system that includes a source of memory access requests and a data storage element. Memory access requests transmitted by the source are temporarily held in a queue prior to transmission to the data storage element. Transmission of memory access requests from the queue to the data storage element is made on the basis of a logical comparison of memory access requests stored in elements of the queue. The logical comparison has as an operand a source priority level included as part of each memory access request stored in the queue, and/or a probability of the data storage element currently being able to service the memory access request if transmitted from the queue to the data storage element at that time.